Everything about Tree-adjoining Grammar totally explained
Tree-adjoining grammar (TAG) is a grammar formalism defined by
Aravind Joshi. Tree-adjoining grammars are somewhat similar to
context-free grammars, but the elementary unit of rewriting is the tree rather than the symbol. Whereas context-free grammars have rules for rewriting symbols as strings of other symbols, tree-adjoining grammars have rules for rewriting the nodes of trees as other trees (see
tree (graph theory) and
tree data structure).
History
TAG originated in investigations by Joshi and his students into the family of adjunction grammars (AG),
the "string grammar" of
Zellig Harris. AGs handle
endocentric properties of language in a natural and effective way, but don't have a good characterization of
exocentric constructions; the converse is true of
rewrite grammars, or
phrase-structure grammar (PSG). In 1969, Joshi introduced a family of grammars that exploits this complementarity by mixing the two types of rules. A few very simple rewrite rules suffice to generate the vocabulary of strings for adjunction rules. This family is distinct from the
Chomsky hierarchy but intersects it in interesting and linguistically relevant ways.
Description
The rules in a TAG are trees with a special leaf node known as the
foot node, which is anchored to a word.
There are two types of basic trees in TAG:
initial trees (often represented as '
') and
auxiliary trees ('
'). Initial trees represent basic valency relations, while auxiliary tree allow for recursion.
Auxiliary trees have the root (top) node and foot node labeled with the same symbol.
A derivation starts with an initial tree, combining via either
substitution or
adjunction. Substitution replaces a frontier node with another tree whose top node has the same label. Adjunction inserts an auxiliary tree into the center of another tree..
The root/foot label of the auxiliary tree must match the label of the node at which it adjoins.
Other variants of TAG allow
multi-component trees, trees with multiple foot nodes, and other extensions.
Complexity and application
Tree-adjoining grammars are often described as
mildly context-sensitive, meaning that they possess certain properties that make them more powerful (in terms of
weak generative capacity) than context-free grammars, but less powerful than
indexed or
context-sensitive grammars. Mildly context-sensitive grammars are conjectured to be powerful enough to model
natural languages while remaining efficiently
parseable in the general case.
Due to their formal weakness, TAG is often used in
computational linguistics and
natural language processing.
A TAG can describe the language of squares (in which some arbitrary string is repeated), and the language
. This type of processing can be represented by an
embedded pushdown automaton.
Languages with cubes (ie triplicated strings) or with more than four distinct character strings of equal length can't be generated by tree-adjoining grammars.
For these reasons, languages generated by tree-adjoining grammars are referred to as
mildly context-sensitive languages.
Further Information
Get more info on 'Tree-adjoining Grammar'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://tree-adjoining_grammar.totallyexplained.com">Tree-adjoining grammar Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
